package tree;

public class Tree {

    static class T{
        public int value;
        public T left;
        public T right;
        public T(int value) {
            this.value = value;
        }

    }
    private T root;
    public T get(int key) {
        T current = root;
        while (current != null && current.value != key) {
            if (current.value > key)
                current = current.left;
            else if (current.value < key)
                current = current.right;
        }
        return current == null ? null : current;
    }

    public void insert (int key) {
        if (root == null) {
            root = new T(key);
            return;
        }
        T current = root;
        T parent = null;
        while (true) {
            parent = current;
            if (key < parent.value) {
                current = current.left;
                if (current == null) {
                    parent.left = new T(key);
                    return;
                }
            } else if (key > parent.value) {
                current = current.right;
                if (current == null) {
                    parent.right = new T(key);
                    return;
                }
            } else
                return;
        }
    }

    public boolean delete (int key) {
        T parent = null;
        T current = root;
        boolean isLeftChild = false;
        while (current != null && current.value != key) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }
        if (current == null)
            return false;

        // case 1: if node to be deleted has no children
        if (current.left == null && current.right == null) {
            if (current == root)
                root = null;
            else if (isLeftChild)
                parent.left = null;
            else
                parent.right = null;
            //case 2: if node to be deleted has only one child
        } else if (current.left == null) {
            if (current == root)
                root = current.right;
            else if (isLeftChild)
                parent.left = current.right;
            else
                parent.right = current.right;
        } else if (current.right == null) {
            if (current == root)
                root = current.left;
            else if (isLeftChild)
                parent.left = current.left;
            else
                parent.right = current.left;
            //case 3: current.left != null && current.right != null
        } else {
            T successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.left = successor;
            else
                parent.right = successor;
        }
        return true;
    }

    public T getSuccessor (T t) {
        T successor = null;
        T successorParent = null;
        T current = t.right;
        while(current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        if (successor != t.right) {
            successorParent.left = successor.right;
            successor.right = t.right;
        }
        return successor;
    }
}
